package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC699 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution_Standard {
        public List<Integer> fallingSquares(int[][] positions) {
            //Coordinate Compression
            //HashMap<Integer, Integer> index = ...;

//            SegmentTree tree = new SegmentTree(sortedCoords.size());
//            int best = 0;
//            List<Integer> ans = new ArrayList();
//
//            for (int[] pos : positions) {
//                int L = index.get(pos[0]);
//                int R = index.get(pos[0] + pos[1] - 1);
//                int h = tree.query(L, R) + pos[1];
//                tree.update(L, R, h);
//                best = Math.max(best, h);
//                ans.add(best);
//            }
//            return ans;
            return new ArrayList<>();
        }
    }

    class SegmentTree {
        int N, H;
        int[] tree, lazy;

        SegmentTree(int N) {
            this.N = N;
            H = 1;
            while ((1 << H) < N) H++;
            tree = new int[2 * N];
            lazy = new int[N];
        }

        private void apply(int x, int val) {
            tree[x] = Math.max(tree[x], val);
            if (x < N) lazy[x] = Math.max(lazy[x], val);
        }

        private void pull(int x) {
            while (x > 1) {
                x >>= 1;
                tree[x] = Math.max(tree[x * 2], tree[x * 2 + 1]);
                tree[x] = Math.max(tree[x], lazy[x]);
            }
        }

        private void push(int x) {
            for (int h = H; h > 0; h--) {
                int y = x >> h;
                if (lazy[y] > 0) {
                    apply(y * 2, lazy[y]);
                    apply(y * 2 + 1, lazy[y]);
                    lazy[y] = 0;
                }
            }
        }

        public void update(int L, int R, int h) {
            L += N;
            R += N;
            int L0 = L, R0 = R, ans = 0;
            while (L <= R) {
                if ((L & 1) == 1) apply(L++, h);
                if ((R & 1) == 0) apply(R--, h);
                L >>= 1;
                R >>= 1;
            }
            pull(L0);
            pull(R0);
        }

        public int query(int L, int R) {
            L += N;
            R += N;
            int ans = 0;
            push(L);
            push(R);
            while (L <= R) {
                if ((L & 1) == 1) ans = Math.max(ans, tree[L++]);
                if ((R & 1) == 0) ans = Math.max(ans, tree[R--]);
                L >>= 1;
                R >>= 1;
            }
            return ans;
        }
    }

    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * 得好好学习一下线段树和坐标压缩啊
     * @return:
     */
    class Solution {
        public class SegmentTree {
            private final int[][] positions;
            private HashMap<Integer, Integer> truthToVirtual;//对应下标
            private int MAXN;
            private int[] change;
            private int[] max;
            private int N;//坐标总数

            public SegmentTree(int[][] positions) {
                this.positions = positions;
                TreeSet<Integer> treeSet = new TreeSet<>();
                for (int[] square : positions) {
                    treeSet.add(square[0]);//左边界
                    treeSet.add(square[0] + square[1] - 1);//右边界
                }
                //编号
                N = 0;
                truthToVirtual = new HashMap<>();
                while (!treeSet.isEmpty()) {
                    truthToVirtual.put(treeSet.pollFirst(), N++);
                }
            /*for(Map.Entry<Integer,Integer> i:truthToVirtual.entrySet()){
                System.out.println("truthIdx:"+i.getKey()+",virtualIdx"+i.getValue());
            }*/
                //初始化各表
                MAXN = N << 2;
                max = new int[MAXN];
                change = new int[MAXN];
            }

            private List<Integer> fallingAll() {
                List<Integer> ans = new ArrayList<>();
                int l, r;
                int max = 0;
                for (int[] square : positions) {
                    l = truthToVirtual.get(square[0]);
                    r = truthToVirtual.get(square[0] + square[1] - 1);
                    int height = query(l, r, 0, N - 1, 1) + square[1];
                    ans.add(max = Math.max(height, max));
                    update(l, r, height, 0, N - 1, 1);
                }
                return ans;
            }


            //从L...R区间下发任务
            private void pushDown(int rt) {
                int leftChild = rt << 1;
                if (change[rt] != 0) {//下发更新任务
                    change[leftChild] = change[rt];
                    change[leftChild | 1] = change[rt];
                    max[leftChild] = change[rt];
                    max[leftChild | 1] = change[rt];
                    change[rt] = 0;
                }
            }

            private void pushUp(int rt, int lc, int rc) {
                //当前区间最高高度肯定是两个子区间中更高那个
                max[rt] = Math.max(max[lc], max[rc]);
            }

            private int query(int l, int r, int L, int R, int rt) {
                if (l <= L && r >= R) {
                    return max[rt];
                }
                //懒不住，任务下发
                int mid = L + ((R - L) >> 1);
                pushDown(rt);
                int ans = 0;
                if (l <= mid) {
                    ans = Math.max(query(l, r, L, mid, rt << 1), ans);
                }
                if (r > mid) {
                    ans = Math.max(query(l, r, mid + 1, R, rt << 1 | 1), ans);
                }
                pushUp(rt, rt << 1, rt << 1 | 1);
                return ans;
            }

            private void update(int l, int r, int c, int L, int R, int rt) {
                if (l <= L && r >= R) {
                    change[rt] = c;//懒住
                    max[rt] = c;
                    return;
                }
                //懒不住，任务下发
                int mid = L + ((R - L) >> 1);
                pushDown(rt);
                if (l <= mid) {
                    update(l, r, c, L, mid, rt << 1);
                }
                if (r > mid) {
                    update(l, r, c, mid + 1, R, rt << 1 | 1);
                }
                pushUp(rt, rt << 1, rt << 1 | 1);
            }
        }

        public List<Integer> fallingSquares(int[][] positions) {
            return new SegmentTree(positions).fallingAll();
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC699 an = new LC699();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
